#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef struct ListNode {
	int val;
	struct ListNode* next;
}ListNode;
ListNode* reverseList(ListNode* head) {
    ListNode* left = NULL;
    ListNode* mid = head;
    ListNode* right;
    while (mid != NULL)
    {
        right = mid->next;
        mid->next = left;
        left = mid;
        mid = right;
    }
    return left;
}
bool isPalindrome(struct ListNode* head) {
    if (head == NULL || head->next == NULL)
        return true;
    ListNode* slow = head;
    ListNode* fast = head;
    ListNode* pre = NULL;
    while (fast != NULL && fast->next != NULL)
    {
        pre = slow;
        slow = slow->next;
        fast = fast->next->next;
    }
    pre->next = reverseList(slow);
    ListNode* cur = pre->next;
    while (head != pre->next)
    {
        if (head->val != cur->val)
            return false;
        else
        {
            head = head->next;
            cur = cur->next;
        }
    }
    return true;
}
void test()
{
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));
    ListNode* h1 = (ListNode*)malloc(sizeof(ListNode));
    ListNode* h2 = (ListNode*)malloc(sizeof(ListNode));
    ListNode* h3 = (ListNode*)malloc(sizeof(ListNode));
    ListNode* h4 = (ListNode*)malloc(sizeof(ListNode));
    head->val = 1;
    h1->val = 2;
    h2->val = 3;
    h3->val = 2;
    h4->val = 1;
    head->next = h1;
    h1->next = h2;
    h2->next = h3;
    h3->next = h4;
    h4->next = NULL;
    printf("%d\n", isPalindrome(head));
}
int main()
{
    test();
	return 0;
}
